05 - Hitra Fourierova transformacija (FFT)¶
Matematično-fizikalni praktikum, november 2023
Luka Skeledžija, 28201079
Uvod¶
Hitra Fourierova transformacija (FFT) je zelo uporabno orodje za analizo različnih vrst signalov. Njene prednosti vključujejo visoko hitrost in nizko porabo pomnilnika. Ti dve lastnosti nam omogočata analizo daljših signalov v primerjavi s standardno diskretno Fourierovo transformacijo (DFT). Z ustrezno implementacijo lahko zmanjšamo časovno zahtevnost iz $N^2$ na $N \log_2 N$, kar je za računalništvo bistvena pohitritev. Fourierove transformacije bomo uporabili za izračun (avto)korelacijskih funkcij, ki so definirane kot:
\begin{equation*} \phi_{gh}(\tau) = \frac{1}{T}\int\limits_0^{T} g(t+\tau)\,h(t)\,dt \>, \end{equation*} ali za diskretne vrednosti \begin{equation*} \phi_{gh}(n) = \frac{1}{N}\sum_{k=0}^{N-1} g_{k+n}\, h_k \>. \end{equation*}
Z uporabo Fourierovih transformacij lahko konvolucijo prevedemo v množenje. Naj bosta $F = \mathcal{F}(f)$ in $G = \mathcal{F}(g)$, nato je korelacijska funkcija podana kot: \begin{equation*} \phi_{gh}(n) = \frac{1}{N-n}\mathcal{F}^{-1} \left[ G \cdot (H)^\ast \right] \end{equation*} Za izračun avtokorelacijske funkcije uporabimo zgornjo enačbo, kjer je $g = h$. Avtokorelacijske funkcije nam bodo prišle prav pri analizi zašumljenih zvočnih signalov.
Naloga¶
Na spletni strani MF praktikuma najdeš posnetke oglašanja velike uharice, naše največje sove. Posneti sta dve sovi z minimalnim ozadjem (${\tt bubomono}$ in ${\tt bubo2mono}$) in nekaj mešanih signalov, ki zakrivajo njuno oglašanje (${\tt mix}$, ${\tt mix1}$, ${\tt mix2}$ in ${\tt mix22}$). V signalih ${\tt mix2}$ in ${\tt mix22}$ je oglašanje sove komaj še zaznavno. Izračunaj avtokorelacijsko funkcijo vseh signalov in poskusi ugotoviti, za katero sovo gre pri teh najbolj zašumljenih signalih!
Princip reševanja¶
- Na podlagi posnetkov izrišemo spektrograme, da si vhodne podatke vizualiziramo.
- Implementiramo autokorelacijsko funkcijo na različne načine in jih med sabo primerjamo.
- Na podlagi zvočnih posnetkov izračunamo njihovo avtokorelacijsko funkcijo in skupaj z uporabo FFT poskusimo določiti sove v posnetkih.
- Dodatek
Vhodni podatki in vizualizacija¶
V Python uvozimo .wav datoteke in jih pretvorimo v numpy array. Določili bomo namreč katera sova nastopa v določenem posnetku.
| Datoteka | Opis | Vzorčenje [kHz] | Določena sova |
|---|---|---|---|
| bubo.wav | Velika uharica Simon | 44.1 | Simon (bubo) |
| bubo2.wav | Velika uharica Garfunkel | 44.1 | Garfunkel (bubo2) |
| mix.wav | Neznana uharica + čricki | 44.1 | ? |
| mix1.wav | Neznana uharica + čricki + potok | 44.1 | ? |
| mix2.wav | Neznana uharica + čricki + deroča reka | 44.1 | ? |
| mix22.wav | Neznana uharica + deroča reka | 44.1 | ? |
Tabela 1: Vhodni podatki.
bubo.wav
bubo2.wav
mix.wav
mix1.wav
mix2.wav
mix22.wav
Spektrogram¶
Na podlagi prebranih posnetkov izrišemo spektrograme. Na prvem spektrogramu (bubo.wav) je skovik sove že na prvi pogled očiten, vendar za ostale posnetke ta sklep ni trivialen. Vseeno ugotovimo, da so iskani signali v rangu do $1\; \text{kHz}$ in vse bolj in bolj zašumljeni.
Avtokorelacijska funkcija¶
Ker imamo opravka z močno zašumljenimi signali, si bomo pri njihovi analizi pomagali z avtokorelacijsko funkcijo. Ker so naši posnetki vzorčeni z relativno visiko vzorčno frekvenco (44.1 kHz), moramo razmisliti o učinkoviti implementaciji. Avtokorelacijsko funkcijo implementiramo na 3 načine in jo testiramo na testnem zašumljenem signalu. Uporabimo 3 različne metode izračuna:
- Po definiciji za diskretne vrednosti v jeziku Python: \begin{equation*} \phi_{hh}(n) = \frac{1}{N - n}\sum_{k=0}^{N-1} h_{k+n}\, h_k \>, \end{equation*}
- Po definiciji z modifikacijo za
numpy, kjer ima signal $h$ dolžine $N$ dodan "zero-padding" dolžine $N$, kar poimenujemo $\tilde{h}$ in zapišemo: \begin{equation*} \phi_{hh}(n) = \frac{1}{N - n}\sum_{k=0}^{2N-1} \tilde{h}_{k+n}\, \tilde{h}_k \>. \end{equation*} - Z uporabo FFT. Naj bo $H = \mathcal{F}(h)$, tedaj je korelacijska funkcija podana kot: \begin{equation*} \phi_{hh}(n) = \frac{1}{N-n}\mathcal{F}^{-1} \left[ \, \mid H \mid^2 \, \right] \end{equation*}
Test izvedemo na funkciji $f$, ki je sestavljena iz vsot in produktov elementarnih funkcij z dodanim šumom.
Iz rezultatov slutimo, da avtokorelacijska funkcija $f$ na nek način "izpovpreči" in tako odstrani šum. Vendar zgodba ni tako preprosta, saj obliki funkcij nista zares primerljivi. Iz primerjave časovne zahtevnosti ugotovimo, da je implementacija z uporabo FFT nekaj velikostnih redov hitrejša od ostalih dveh algoritmov. Odločimo se za uporabo FFT.
Analiza frekvenčnega spektra¶
Sove bomo verjetno najlažje razločili na podlagi frekvence skovika. Zato neobdelan posnetek z uporabo FFT pretvorimo v frekvenčni spekter. Ugotovimo, da so signali precej zašumljeni, šum pa je prisoten predvsem pri nižjih frekvencah. Kot smo ugotovili iz spektrogramov, nas zanima predvsem območje do 1 kHz. Iz prvih dveh jasnih posnetkov (bubo in bubo2) opazimo porast amplitude pri ~ 335 Hz in ~375 Hz. Vendar so nekateri signali še vedno preveč zašumljeni, da bi lahko sove zanesljivo ločili.
V nadaljevanju za zvočne posnetke izračunamo relativno avtokorelacijsko funkcijo
\begin{equation*} \widetilde{\phi}_{hh}(n) = { \phi_{hh}(n) - \langle h\rangle^2 \over \phi_{hh}(0) - \langle h\rangle^2 } \>, \end{equation*}
kjer je
\begin{equation*}
\langle h\rangle = \frac{1}{N} \sum_{k=0}^{N-1} h_k \>.
\end{equation*}
Na spodnjem grafu prikažemo $| \widetilde{\phi}_{hh} |$.
Ker si tudi iz tega grafa ne znamo pomagati, ponovno uporabimo FFT in avtokorelacijsko funkcijo pretvorimo v frekvenčni spekter.
Z uporabo avtokorelacije smo se precej uspešno znebili šuma. Še vedno pa nekatere "špice" (mix22) niso pretirano izrazite. Avtokorelacijo uporabimo še enkrat.
Na zadnjem grafu lahko končno zanesljivo razberemo frekvence skovikov, in sicer $(335 \pm 10) \; \text{Hz}$ za sovo Simona in $(375 \pm 10) \; \text{Hz}$ za Garfunkla. Na podlagi tega izpolnimo spodnjo tabelo in v vsakem posnetku določimo nastopajočo sovo.
| Datoteka | Opis | Določena sova |
|---|---|---|
| bubo.wav | Velika uharica Simon | Simon (bubo) |
| bubo2.wav | Velika uharica Garfunkel | Garfunkel (bubo2) |
| mix.wav | Neznana uharica + čricki | Simon (bubo) |
| mix1.wav | Neznana uharica + čricki + potok | Simon (bubo) |
| mix2.wav | Neznana uharica + čricki + deroča reka | Simon (bubo) |
| mix22.wav | Neznana uharica + deroča reka | Garfunkel (bubo2) |
Tabela 2: Rezultati analize zvoka.
Dodatek: S kakšno frekvenco prede Henry?¶
In the whimsical realm of quantum catodynamics, physicists have long pondered the enigmatic phenomenon of cat purring. According to the interstellar "Hitchhiker's Guide to the Galaxy," cats have been granted the rare ability to oscillate at a quantum frequency that transcends the boundaries of Schrödinger's box. It's not just a soothing sound; it's a cosmic symphony that defies the laws of physics as we know them. Some quantum quirk in the feline waveform allows cats to simultaneously purr and not purr, rendering them in a state of purrplexity, or what scientists affectionately refer to as "Schrödinger's Cat Purradox." It's a profound reminder that the universe is full of surprises, especially when it comes to our feline friends and their quantum serenades.
V dodatku poskusimo odgovoriti na dolgo pereče vprašanje... s kakšno frekvenco prede Henry?
cat.wav
Določena frekvenca $\nu_{\text{p}} = 130 \; \text{Hz} \; \pm \; 10 \; \text{Hz}$ Henryja uvršča med višje-frekvenčne predilce, saj se tipični spekter razpenja med 20 in 150 Hz.
Zaključek¶
Z uporabo FFT in izračunom funkcije avtokorelacije smo v frekvenčni sliki uspešno ločili med dvema signaloma različnih frekvenc tudi v najbolj zašumljenih primerih. Primerjali smo različne metode za izračun avtokorelacije in ugotovili, da je izračun s pomočjo FFT najbolj učinkovit.
Luka Skeledžija, Github source 🔗, 2023